/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-22
 * Time: 13:15
 */
class Solution1 {
    public int countSubstrings(String s) {
        char[] str = s.toCharArray();
        int n = s.length();
        //1.创建dp表
        //dp[i,j]区间[i,j]是否为回文串
        boolean[][] dp = new boolean[n][n];
        //无需初始化
        //3.状态转移
        int count = 0;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(str[i] != str[j]) {
                    dp[i][j] = false;
                }else if(str[i] == str[j]) {
                    if(i == j) {
                        dp[i][j] = true;
                    }else if(i+1 == j) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] == true) {
                    count++;
                }
            }
        }
        //4.从下到上
        //5.返回值
        return count;
    }
}
